﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

using BaseClasses;

namespace Djikstria
{
    /// <summary>
    /// 
    /// </summary>
    public class ShortestPathAlgorithm
    {
        /// <summary>
        /// 
        /// </summary>
        /// <param name="startVertex"></param>
        /// <param name="finishVertex"></param>
        /// <param name="graph"></param>
        /// <returns></returns>
        public static IEnumerable<Vertex> FindShortestPath(Vertex startVertex, Vertex finishVertex, Graph graph)
        {
            // Checking arguments
            if (startVertex == null || finishVertex == null || graph == null)
                throw new ArgumentNullException();
            if (startVertex.Symbol == finishVertex.Symbol)
                throw new Exception("Vertexes have the same symbol.");
            if (graph.Count <= 0)
                throw new Exception("Graph has zero or less links");
            if (!Vertex.ContainsVertex(graph.Vertexes, startVertex) || !Vertex.ContainsVertex(graph.Vertexes, finishVertex))
                throw new Exception("One of the given vertexes is not present in given graph.");

            // Preparing variables
            Graph pathGraph = new Graph(); // Collection of all shortest paths from startVertex to finishVertex. The collection starts with only one graph.
            Vertex currentVertex = null;
            ICollection<Vertex> solvedVertexes = new List<Vertex>(); // 
            ICollection<Link> candidateLinks = null;
            Dictionary<Vertex, int> vertexPathCosts = new Dictionary<Vertex, int>(); // 

            // Prepare first vertex
            currentVertex = (Vertex)graph.Vertexes.First(x => x.Symbol == startVertex.Symbol);
            currentVertex.Visited = true;
            vertexPathCosts.Add(currentVertex, 0);
            solvedVertexes.Add(currentVertex);


            while (currentVertex != null)
            {
                Console.WriteLine("Current vertex: {0}", currentVertex.Symbol);

                // Prepare candidateLinks collection
                if (candidateLinks == null)
                    candidateLinks = new List<Link>();
                else
                    candidateLinks.Clear();

                // Prepare link paths cost bidictionary
                var pathCosts = new Dictionary<Link, int>();

                /* Pkt 3. Znajdujemy wszystkie wierzchołki, do których możemy przejść z wierzchołków, w których już byliśmy. */

                // Get links for all solved vertexes
                foreach (Vertex solvedVertex in solvedVertexes)
                {
                    var solvedVertexesLinks = graph.GetVertexesLinks(solvedVertex);
                    foreach (Link candidateLink in solvedVertexesLinks)
                        if (!Link.ContainsLink(candidateLinks, candidateLink)
                            && !(candidateLink.Alfa.Visited && candidateLink.Omega.Visited))
                        {
                            // Add candidate link to collection
                            candidateLinks.Add(candidateLink);

                            /* Pkt 4. Dla kązdego wierzchołka obliczamy koszt przejścia */

                            // Calculate and add path cost (vertexes path + link)
                            int vertexPathCost = 0;

                            if ((candidateLink.Alfa.Symbol == "E" && candidateLink.Omega.Symbol == "G") || (candidateLink.Alfa.Symbol == "E" && candidateLink.Omega.Symbol == "F"))
                            {
                                System.Diagnostics.Debug.WriteLine("Watch out");
                            }

                            // Check is Alfa in 
                            if (vertexPathCosts.Any(x => x.Key == candidateLink.Alfa))
                            {
                                int travelCost = vertexPathCosts.First(x => x.Key.Symbol == candidateLink.Alfa.Symbol).Value;
                                vertexPathCost = travelCost + candidateLink.Cost;
                            }
                            else if (vertexPathCosts.Any(x => x.Key == candidateLink.Omega))
                            {
                                int travelCost = vertexPathCosts.First(x => x.Key.Symbol == candidateLink.Omega.Symbol).Value;
                                vertexPathCost = travelCost + candidateLink.Cost;
                            }
                            else
                                throw new Exception("Vertexes path cost was not found!");

                            pathCosts.Add(candidateLink, vertexPathCost);
                        }
                }

                /* Pkt 5. Wybieramy wierzchołek, do którego koszt przejścia okazał się być najmniejszy */

                // Choose vertexes with the shortest path
                ICollection<Link> theCheapestLinksCollection = new List<Link>(); // Wierzchołki o najmniejszym koście przejścia.
                Link theCheapestLink = null;

                pathCosts = pathCosts.OrderBy(x => x.Value).ToDictionary(x => x.Key, x => x.Value);
                foreach (Link link in pathCosts.Keys)
                {
                    if (theCheapestLink != null)
                    {
                        if (pathCosts[link] <= pathCosts[theCheapestLink])
                            theCheapestLink = link;
                    }
                    else
                        theCheapestLink = link;

                    if (pathCosts[link] == pathCosts[theCheapestLink])
                        theCheapestLinksCollection.Add(theCheapestLink);
                }

                if (theCheapestLinksCollection.Count == 0)
                    throw new Exception("Choosing the cheapest link has failed.");

                Vertex choosenVertex = theCheapestLink.Alfa.Visited ? theCheapestLink.Omega : theCheapestLink.Alfa;
                Vertex sourceVertex = !theCheapestLink.Alfa.Visited ? theCheapestLink.Omega : theCheapestLink.Alfa;
                choosenVertex.PreviousVertex = sourceVertex;
                solvedVertexes.Add(choosenVertex);

                choosenVertex.TravelCost = sourceVertex.TravelCost + theCheapestLink.Cost;
                vertexPathCosts.Add(choosenVertex, theCheapestLink.Cost + sourceVertex.TravelCost);

                currentVertex = choosenVertex;
                currentVertex.Visited = true;
                pathGraph.Add(theCheapestLink);

                if (choosenVertex.Symbol == finishVertex.Symbol)
                    currentVertex = null;
                else
                    currentVertex = choosenVertex;
            }


            Stack<Vertex> sv = new Stack<Vertex>();

            Vertex _vertex = solvedVertexes.First(x => x.Symbol == finishVertex.Symbol);
            sv.Push(_vertex);
            while (_vertex.PreviousVertex != null)
            {
                sv.Push(_vertex.PreviousVertex);
                _vertex = _vertex.PreviousVertex;
            }

            return sv;
        }
    }
    public static class StackMixin
    {

        public static ICollection<Link> CleanUp(this Graph graph, Vertex start, Vertex finish)
        {
            ICollection<Link> newCollection = new List<Link>();

            if (graph == null)
                throw new ArgumentNullException();
            if (graph.Links.Count < 3)
                throw new Exception("Not enough links to clean up!");

            ICollection<Vertex> deadends = new List<Vertex>();



            //              // Select the numberous item
            //              var mostCommonVertexCount = vertexes.GroupBy(x => x).OrderByDescending(grp => grp.Count())
            //.Select(grp => grp.Key).First();
            //              int numberOfItem = vertexes.Count(x => mostCommonVertexCount == x);



            return newCollection;
        }


        public static Stack<T> Clone<T>(this Stack<T> stackToClone)
        {
            if (stackToClone == null)
                throw new ArgumentNullException();

            IEnumerable<T> reversedStackToClone = stackToClone.Reverse<T>();
            Stack<T> cloneStack = new Stack<T>(reversedStackToClone);
            return cloneStack;
        }

        public static Stack<Link> CleanUp(this Stack<Link> linkStack)
        {
            if (linkStack == null || linkStack.Count == 0)
                throw new ArgumentNullException();

            if (linkStack.Count < 3)
                throw new Exception("There is nothing to clean up!");

            Stack<Link> reversedStack = new Stack<Link>();
            Link prevLink = null;
            Link actualLink = null;
            Link nextLink = null;

            actualLink = linkStack.Pop();
            reversedStack.Push(actualLink); // Push top first link to the reversed stack
            try
            {
                while (true)
                {
                    prevLink = actualLink;
                    actualLink = linkStack.Pop();
                    nextLink = linkStack.Peek();

                    Link[] links = { prevLink, actualLink, nextLink };

                    // Check is the actual link connected with previous one and next one
                    // Calculate number of vertexes in those two links, if there is more than 4, then there is a branch
                    List<Vertex> vertexes = new List<Vertex>();

                    foreach (Link link in links)
                    {
                        vertexes.Add(link.Alfa);
                        vertexes.Add(link.Omega);
                    }

                    // Select the numberous item
                    var mostCommonVertexCount = vertexes.GroupBy(i => i).OrderByDescending(grp => grp.Count())
      .Select(grp => grp.Key).First();
                    int numberOfItem = vertexes.Count(x => mostCommonVertexCount == x);

                    if (numberOfItem <= 2)
                    {
                        reversedStack.Push(actualLink);
                    }
                }
            }
            catch (InvalidOperationException) { }

            reversedStack.Push(actualLink); // Push remaining last link to the reversed stack

            return new Stack<Link>(reversedStack.Reverse()); // return cleaned up stack
        }

        public static ICollection<Stack<Link>> CleanUpStacks(this ICollection<Stack<Link>> stacks)
        {
            ICollection<Stack<Link>> newCollection = new List<Stack<Link>>();

            foreach (Stack<Link> stack in stacks)
            {
                Stack<Link> newStack = stack.Clone<Link>();
                try
                {
                    newStack = newStack.CleanUp();
                }
                catch (Exception) { }
                newCollection.Add(newStack);
            }

            return newCollection;
        }

        public static bool IsConnectedWith(this Link thatLink, Link link)
        {
            return thatLink.Alfa == link.Alfa || thatLink.Alfa == link.Omega
                || thatLink.Omega == link.Alfa || thatLink.Omega == link.Omega;
        }
    }
}
